package com.julius.design.suanfa.search;

import java.util.HashSet;
import java.util.Set;

/**
 * @author julius
 * @date 2021-10-22 上午 9:55
 * <p>
 *      查找任意一个重复数字
 *      https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
 * </p>
 */
public class FindRepeatNumber {
    /**
     * 查找重复数字
     * @param nums 数组
     * @return 任意一个重复数字
     */
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            //当前索引和索引上的数字相同，指针后移一位
            if (nums[i] == i) {
                i++;
                continue;
            }
            if (nums[nums[i]] == nums[i]) {
                //如果当前值所在位置和当前数字相同，则重复，返回当前值。这里为何这么做呢》》》
                return nums[i];
            }
            //将当前值放到当前值的位置上（1000应该放在999的索引上）。此时不经行索引后移
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return -1;
    }
}
